package com.mlh.binarytree.ACM;

import com.mlh.binarytree.TreeNode;
import com.mlh.binarytree.search.InorderTraversal;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author 缪林辉
 * @date 2024/10/24 16:22
 * @DESCRIPTION
 */
public class ACM构造二叉树 {

    public static void main(String[] args) {
        TreeNode root = ACM构造二叉树.buildTree(new int[]{1, 2, 3, -1, 5, 6, -1});
        //利用中序遍历验证一下
        InorderTraversal inorderTraversal = new InorderTraversal();
        List<Integer> list = inorderTraversal.method1(root);
        for (int a : list) {
            System.out.print(a+" ");
        }
    }


    //输入一个完全二叉树数组，-1代表为null
    public static TreeNode buildTree(int[]tree){
        TreeNode root = new TreeNode(tree[0]);
        Queue<TreeNode>queue=new LinkedList<>();
        queue.add(root);
        int index=0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            index++;
            int left=2*index-1;
            int right=2*index;
            if(left<tree.length&&tree[left]!=-1){
                TreeNode leftNode = new TreeNode(tree[left]);
                node.left=leftNode;
                queue.offer(leftNode);
            }
            if(right<tree.length&&tree[right]!=-1){
                TreeNode rightNode = new TreeNode(tree[right]);
                node.right=rightNode;
                queue.offer(rightNode);
            }
        }
        return root;
    }
}
